package lc;

public class Ex208_2 {
    class Trie {
        private Node root;
        public Trie() {
            root = new Node();
        }
        
        public void insert(String word) {
            Node cur = root;
            for (char c: word.toCharArray()) {
                cur.addPath();
                Node next = cur.setNext(c);
                cur = next;
            }
            cur.setEnd();
        }
        
        public boolean search(String word) {
            Node cur = root;
            for (char c: word.toCharArray()) {
                if (cur == null) {
                    return false;
                }
                cur = cur.getNext(c);
            }
            return cur.isEnd();
        }
        
        public boolean startsWith(String prefix) {
            int num = root.getPath();
            Node cur = root;
            char[] cs = prefix.toCharArray();
            for (int i = 0; i < cs.length; i++) { 
                char c = cs[i];
                if (cur.getPath() != num) {
                    return false;
                }
                cur = cur.getNext(c);
            }
            return true;
        }
    }

    class Node {
        private Node[] nexts;
        private int path;
        private boolean isEnd;

        public Node() {
            nexts = new Node[26];
            path = 0;
            isEnd = false;
        }

        public Node getNext(char c) {
            return nexts[c - 'a'];
        }

        public boolean isEnd() {
            return this.isEnd;
        }

        public void setEnd() {
            this.isEnd = true;
        }

        public void addPath() {
            path++;
        }

        public int getPath() {
            return this.path;
        }

        public Node setNext(char c) {
            Node node;
            if ((node = getNext(c)) == null) {
                node = new Node();
                nexts[c - 'a'] = node;
            }
            return node;
        }
    }
}
